package algorithms.graph;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;

public class LazyPrimMST {

	private boolean[] marked;
	private LinkedList<Edge> mst;
	private PriorityQueue<Edge> pq;
	
	/*
	 * there is no need.
	 * Edge 已经实现Comparable接口
	 */
	Comparator<Edge> cm = new Comparator<Edge>() {
		@Override
		public int compare(Edge o1, Edge o2) {
			if(o1.weight() < o2.weight())	return -1;
			else if(o1.weight() > o2.weight())	return 1;
			else									return 0;
		}
	};
	
	public LazyPrimMST(EdgeWeightGraph g) {
		pq = new PriorityQueue<Edge>();
		marked = new boolean[g.V()];
		mst = new LinkedList<Edge>();
		
		visit(g, 0);
		while(!pq.isEmpty()){
			Edge e = pq.poll();
			
			int v = e.either();
			int w = e.other(v);
			if(marked[v] && marked[w]) continue;	//跳过失效的边
			mst.add(e);
			if(!marked[v])	visit(g, v);
			if(!marked[w])	visit(g, w);
		}
	}
	
	private void visit(EdgeWeightGraph g, int v) {
		marked[v] = true;
		for(Edge e : g.adj(v)){
			if(!marked[e.other(v)]) pq.add(e);
		}
	}
	
	public static void main(String[] args) {
		PriorityQueue<Edge> p = new PriorityQueue<Edge>();
		Edge e1 = new Edge(0, 1, 10.1);
		Edge e2 = new Edge(1, 2, 20.3);
		Edge e3 = new Edge(2, 3, 5.3);
		p.add(e1);
		p.add(e2);
		p.add(e3);
		System.out.println(p);
	}
}
